package LearnAlgorithm.g_数学问题;

import java.util.Arrays;
import java.util.Scanner;

/*
 每次玩家都会选择一个棋子，并将其向左移动，而不会越过任何其他棋子或越过左边缘。
 玩家可以自由选择棋子移动的步数，但有一个限制，即棋子必须移动至少一步，一个网格最多可以包含一个棋子。
 不能移动的玩家会输掉比赛。
Sample Input
2 					--几组数据
3 					--第一组数据的数组长度
1 2 3 				--数组
8 					--第二组数据的数组长度
1 5 6 7 9 12 14 17 	--数组
Sample Output
Bob will win		--第一组结果
Georgia will win	--第二组结果
*/
public class bNim游戏other阶梯棋子 {
	public static void main(String[] args) {
//		int[] arr = new int[] {3,4,5};
//		System.out.println("先手方：" + solveNim(arr));
		stepNim();
		
	}
	
	/**
	 * data[i] 每组数据的数组；我们自己在给数据的时候，我们一般都是按升序顺序给
	 * 但是出题人不会，会乱序给
	 * data[i] 中存放的元素，元素数值的含义是“在无限大的棋盘上的第'data[i]'位置有一个棋子”
	 * 举例就是data[i] = {1, 20, 300};
	 * 那么在无限大的棋盘上，在第1个位置，第20个位置，第300个位置分别有1个旗子，无限大棋盘共3个棋子
	 * @param arr
	 */
	public static void stepNim() {
		Scanner scanner = new Scanner(System.in);
		int caseNum = scanner.nextInt();//caseNum 几组数据
		int[][] data = new int[caseNum][];
		for (int i = 0; i < caseNum; i++) {
			int arrLen = scanner.nextInt();//arrLen 每组数据的数组长度
			data[i] = new int[arrLen];//data[i] 每组数据的数组
			for (int j = 0; j < arrLen; j++) {
				data[i][j] = scanner.nextInt();//填充data[i]
			}
		}
		for (int i = 0; i < caseNum; i++) {
			String res = deal(data[i]);
			System.out.println(res);
		}
	}
	
	/**
	 * 判断Nim游戏结果的核心方法
	 * @param arr
	 * @return
	 */
	public static String deal(int[] arr) {
		int len = arr.length;
		int res = 0;
		Arrays.sort(arr);//因为出题人给的数组中的元素是随机存放的，所以我们要先排序
		//阶梯Nim问题需要分奇偶数讨论；但最终仍然使用到异或来解决
		if ((len & 1) == 1) {//(len & 1) == 1 判断len是奇数true，偶数false
			for (int i = 0; i < len; i += 2) {//奇数true
				//下标1，2为一组；下标3，4为一组....下标0单独考虑
				//即第2，3元素为一组；第4，5元素为一组....第1个元素单独考虑
				//如果arr[i] = 4,那么arr[i]这个元素前面有3个元素，即距离是3；
				//arr[i+1]=6，那么arr[i+1]于arr[i]之间的距离是(6 - 4) - 1 = 1；
				res ^= (i == 0) ? (arr[0] - 1) : (arr[i] - arr[i - 1] - 1);
			}
		} else {//偶数false
			for (int i = 1; i < len; i += 2) {
				//下标0，1为一组；下标2，3为一组...
				//即第1，2元素为一组；第3，4元素为一组....
				res ^= (arr[i] - arr[i - 1] - 1);
			}
		}
		if (res == 0) {//res == 0 先手输，这一点和普通Nim游戏算法一致
			return "后手win";
		} else {
			return "先手win";
		}
	}
	
	public static boolean solveNim(int[] arr) {
		int res = 0;
		for (int i = 0; i < arr.length; i++) {
			res ^= arr[i];
		}
		return res != 0;
	}
}
